This application is based upon and claims priority from prior French Patent Application No. 98-16156, filed Dec. 17, 1998, the entire disclosure of which is herein incorporated by reference.
1. Field of the Invention
The present invention relates to electronic systems, and more specifically to a buffer for adapting the data flows exchanged between multiple communication channels.
2. Description of Related Art
An input channel and one or more output channels forming a communication channel are generally asynchronously processed intermittently, so that the input channel often provides data while the output channel is not ready to receive it, or conversely, the output channel is ready to receive data while the input channel provides none. It is thus necessary to adapt the data flows of these channels, which is generally done by using a buffer. The buffer stores any excess data that the output channel cannot accept at a given time and provides the data to the output channel when the channel becomes available.
FIG. 1 illustrates a buffer for adapting the flows of multiple input channels to multiple respective output channels. It can be, for example, a multi-protocol switch for switching multiple ATM connections on multiple Ethernet links. The buffer includes a DRAM 10 which, in high rate applications, is generally a synchronous DRAM (SDRAM). Memory 10 is managed by a memory controller 12 which processes the data exchanged between the ATM connections and the Ethernet links via adequate interfaces 14.
One way of adapting the flows of multiple communication channels is to dedicate an area of fixed size in SDRAM 10 to each possible communication channel. This solution is far from being optimal from the point of view of the memory use, since a seldom required dedicated area cannot be used to relieve a very frequently required dedicated area. Thus, dedicated areas must be of maximum size to fulfill possible maximum requirements, although this maximum size will most often not be used. Further, in a switch, the number of open communication channels is variable, and they are practically never all in use at the same time. The areas dedicated to the non-open channels remain empty but are unusable for other channels.
FIG. 2 illustrates another solution for providing a buffer function to each of several possible communication channels. As illustrated, SDRAM 10 is organized in small blocks 16 of fixed size which are dedicated one by one to each communication channel according to needs. More specifically, each communication channel is associated with a chain of linked blocks 16 containing the data waiting for the corresponding output channel, with the chain forming a buffer of variable size. The blocks left free and not assigned to communication channels are listed in a queue of free blocks 18 also contained in memory 10.
To manage this memory organization, memory controller 12 includes, for each possible communication channel, two pointers wbptr and W for the input channel, and two pointers rbptr and R for the output channel. Pointer wbptr points to the last block of the chain, that is, the block which is being filled. Pointer W points to the current writing location of this last block. Pointer rbptr points to the first block of the chain, that is, the block which is being emptied. Pointer R points to the current reading location of this first block. Further, controller 12 includes registers to enable managing of the queue of free blocks 18. Queue 18 may be of the LIFO type (as shown), in which case one register containing a pointer xe2x80x9ctopxe2x80x9d to the top of queue 18 is enough.
Initially, free block queue 18 is full, which signifies that all the blocks of SDRAM 10 are free and can be dedicated to communication channels. When a communication channel is opened, the free block found at the top of queue 18, as indicated by pointer xe2x80x9ctopxe2x80x9d, is dedicated thereto. Pointer xe2x80x9ctopxe2x80x9d is decremented by one unit and the pointers wbptr and rbptr associated with the communication channel are both reset to point to the block just dedicated. At this time, pointers W and R point to the first element to be read from or mitten into the block. After writing a word into the block at the location indicated by pointer W, pointer W is incremented by one unit.
When the last location of the current block is reached by pointer W, a new block taken from the top of queue 18 at the location indicated by pointer xe2x80x9ctopxe2x80x9d is dedicated to the communication channel. Pointer xe2x80x9ctopxe2x80x9d is decremented by one unit, pointer wbptr is updated to point to the new block, pointer W is updated to point to the first location of the new block, and a descriptor of the block just filled is updated to chain to the new block. Thus, if the buffer needs for a communication channel increase, an increasing number of blocks can be used to form a chain, the length of which can increase to occupy the entire SDRAM or at least the entire space left free by the concurrent communication channels, if necessary.
The data to be sent to the output channel is read at the location indicated by pointer R in the block indicated by pointer rbptr. Upon each reading of a word, pointer R is incremented by one unit. When pointer R reaches the last location, pointer rbptr is updated to point to the next block of the chain. Pointer R is updated to point to the first datum to be transmitted in this block. The freed block is inscribed at the top of queue 18, at location top+1. Pointer xe2x80x9ctopxe2x80x9d is then incremented by one unit. Thus, as blocks are freed in a chain associated with a communication channel, these blocks become immediately available to all communication channels.
A problem which arises with such a memory organization is that a single immediate access to free block queue 18 is required. This is particularly impairing in access time when an SDRAM is used, because a minimal access to an SDRAM costs 8 clock cycles, only a single cycle of which is necessary for reading or writing a word. More specifically, there are three preload cycles, three addressing cycles, a read or write cycle, and a stop cycle. Further, free block queue 18 cannot be integrated in controller 12 as a memory accessible in a single cycle, because this queue is generally of too large a size for such an integration to be reasonable.
In view of these drawbacks, it is an object of the present invention to overcome the above-mentioned drawbacks and to provide a memory organization for a buffer that optimizes the accesses to a queue of free blocks contained in a DRAM with an access latency.
Another object of the present invention is to provide a method of managing a buffer for adapting the flows of multiple input channels to multiple respective output channels.
One embodiment of the present invention provides a buffer for adapting data flows from input channels to output channels. The buffer includes a DRAM organized in blocks and a memory controller for managing assignment of the blocks to the chains of linked blocks. The DRAM contains, as a chain of linked blocks, data associated with each communication channel formed by a pair of input and output channels, and also contains a main queue of free blocks for listing unoccupied blocks. The memory controller includes a cache memory containing a partial queue of free blocks that the memory controller uses in managing block assignment. According to one embodiment, when a level of the partial queue reaches a predetermined minimum limit the cache memory is at least partially filled by a burst from the main queue, and when a level of the partial queue reaches a predetermined maximum limit the cache memory is at least partially emptied by a burst into the main queue. According to another embodiment, the partial queue stores a local image of a top portion of the main queue, and the memory controller exclusively uses the partial queue in assigning blocks to the chains of linked blocks.
Another embodiment of the present invention provides a method of managing a buffer for adapting data flows from input channels to output channels. According to the method, first elements are initially transferred from a main queue of free blocks to a cache memory and corresponding access pointers of the cache memory and the main queue are updated. A free block is assigned by taking it from the cache memory while decrementing the cache memory access pointer, and a block is freed by putting it in the cache memory while incrementing the cache memory access pointer.
Yet another embodiment of the present invention provides a method of managing a buffer for adapting data flows from input channels to output channels. According to the method, first elements are initially transferred from a main queue of free blocks to a cache memory and corresponding access pointers of the cache memory and the main queue are updated. When the cache memory access pointer reaches a predetermined minimum limit, the next elements of the main queue are transferred to the cache memory in a burst, so as to at least partially fill the cache memory. Additionally, when the cache memory access pointer reaches a predetermined maximum limit, the cache memory is at least partially emptied into the main queue by a burst.
Other objects, features, and advantages of the present invention will become apparent from the following detailed description. It should be understood, however, that the detailed description and specific examples, while indicating preferred embodiments of the present invention, are given by way of illustration only and various modifications may naturally be performed without deviating from the present invention.